package com.mystudy.leetcode.problem.link.p_234;

import com.mystudy.leetcode.base.ListNode;
import com.mystudy.leetcode.base.ListNodeUtils;
import org.junit.Test;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

/**
 * @author 周志龙
 * @Email 15216876513@163.com
 * @Date on 2019/7/5 19:59
 * @Description 回文链表
 */
public class Solution {
    private static final Logger LOGGER = LoggerFactory.getLogger(Solution.class);

    @Test
    public void testPalindrome() {
        ListNode listNode = ListNodeUtils.generateLinkList(new int[]{1, 2,3, 2, 1});
        boolean palindrome = isPalindrome(listNode);
        LOGGER.debug("palindrome = [ {} ]", palindrome);
    }

    public boolean isPalindrome(ListNode head) {
        ListNode fast = head;
        ListNode lazy = head;
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode prev = dummyHead;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            lazy = lazy.next;
            prev = prev.next;
        }
          /*  1,2,2,1
                    1,2,3,2,1*/
        //此时lazy在中间节点,prev在lazy节点的前一个节点
        //从中间节点反转后面的列表

        ListNode cur = lazy;
        ListNode temphead = lazy;
        while (cur != null && cur.next != null) {
            ListNode nextTemp = cur.next;
            cur.next = nextTemp.next;
            nextTemp.next = temphead;
            temphead = nextTemp;
        }
        prev.next = temphead;


        //如果两个链表的每一个节点的数据都相等，或者前一个链表遍历完都相等并且只剩一个节点也是回文
        ListNode prevCur = head;
        ListNode nextCur = temphead;
        while (prevCur != temphead) {
            if (prevCur.val != nextCur.val) {
                break;
            }
            prevCur = prevCur.next;
            nextCur = nextCur.next;
        }
        //代表走到了最后
        if (prevCur == temphead) {
            if (nextCur == null || nextCur.next == null) {
                return true;
            }
        }
        return false;
    }

}
